package pfq.demo.algorithm.linkedlist;

/**
 * 链表反转
 */
public class Practice2 {

    /**
     * 链表中的结点
     */
    static class Node {
        Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        int data;
        Node next;
    }

    static void reverse(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }

        Node p = head.next;
        Node q = p.next;
        p.next = null;// 这行代码很重要，没有这行的话，在遍历反转后的链表时会出现死循环
        while (q != null) {
            Node r = q.next;
            q.next = p;
            p = q;
            q = r;
        }

        head.next = p;
    }

    /**
     * 打印链表
     */
    static void printNode(Node head) {
        if (head == null || head.next == null) {
            System.out.println("链表为空");
            return;
        }

        Node p = head.next;
        System.out.print("链表中的数据：");
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();

    }

    public static void main(String[] args) {

        // 初始化一条链表
        Node head = new Node(-1, null);
        Node p = head;
        for (int i = 0; i < 5; i++) {
            Node node = new Node(i + 1, null);
            p.next = node;
            p = p.next;
        }

        printNode(head);

        reverse(head);

        printNode(head);
    }

}
